/*
 *https://leetcode.cn/problems/strange-printer/
 *664. 奇怪的打印机
 *medium 吴朝泽 2024.10.9
 *区间DP
*/

class Solution {
public:
    int strangePrinter(string s) 
    {
        int n = s.size();  // 获取输入字符串的长度
        int dp[n][n];      // 创建一个二维数组，用于存储打印子字符串的最小次数
        memset(dp, 0x3f, sizeof(dp)); // 将 dp 数组初始化为一个大值（无穷大）

        for (int i = n - 1; ~i; --i)  // 从字符串末尾向开头遍历
        {
            dp[i][i] = 1; // 如果只打印一个字符，则只需要 1 次打印
            
            // 遍历可能的结束位置 j
            for (int j = i + 1; j < n; ++j) 
            {
                // 如果 s[i] 和 s[j] 相同，可以将它们一起打印
                if (s[i] == s[j]) 
                    dp[i][j] = dp[i][j - 1]; // 直接继承前一个结果
                else 
                {
                    // 如果它们不同，需要考虑不同的划分
                    for (int k = i; k < j; ++k) 
                        // 通过划分字符串，找到最小打印次数
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
};
